package acwing._1_1AlgorithmBasic;

/**
 * @Project : ProgrammingExercises
 * @Package : ACWing.Learning.AlgorithmTemplate
 * @File : _2_1LinkedList.java
 * @Author : WangRuoyu
 * @Date 2023/3/11 15:54
 */

// 数组模拟链表 静态链表
public class _2_1LinkedList {

}

// 单链表
class singleLinkedList {
    private final int head;
    private int idx;
    int[] val = new int[100010];
    int[] next = new int[100010];

    public singleLinkedList() {
        head = 0;
        next[head] = -1;
        idx = 1;
    }

    public void add_to_head(int x) {
        val[idx] = x;
        next[idx] = next[head];
        next[head] = idx;
        idx++;
    }

    public void add(int index, int x) {
        val[idx] = x;
        next[idx] = next[index];
        next[index] = idx;
        idx++;
    }

    public void remove(int index) {
        next[index] = next[next[index]];
    }

    public int myHead() {
        return head;
    }
}

// 双链表
class doubleLinkedList {
    private final int head, tail;
    private int idx = 0;
    int[] val = new int[100010];
    int[] next = new int[100010];
    int[] pre = new int[100010];

    public doubleLinkedList() {
        head = 0;
        tail = 1;
        idx = 2;

        next[head] = tail;
        next[tail] = head;
        pre[head] = tail;
        pre[tail] = tail;
        val[head] = -1;
        val[tail] = -1;
    }

    public void add_next(int index, int val) {
        this.val[idx] = val;
        next[idx] = next[index];
        pre[idx] = index;
        pre[next[index]] = idx;
        next[index] = idx;
        idx++;
    }

    public void remove(int index) {
        next[pre[index]] = next[index];
        pre[next[index]] = pre[index];
    }

    public int myHead() {
        return head;
    }

    public int myTail() {
        return tail;
    }
}

// 双链表
class circularSingleLinkedList {
    private final int head;
    private int idx;
    int[] val = new int[100010];
    int[] next = new int[100010];

    public circularSingleLinkedList() {
        head = 0;
        next[head] = head;
        idx = 1;
    }

    public void add_to_head(int x) {
        val[idx] = x;
        next[idx] = next[head];
        next[head] = idx;
        idx++;
    }

    public void add(int index, int x) {
        val[idx] = x;
        next[idx] = next[index];
        next[index] = idx;
        idx++;
    }

    public void remove(int index) {
        next[index] = next[next[index]];
    }

    public int myHead() {
        return head;
    }
}
